Analysis of Autonomous Systems

AA120Q: Building Trust in Autonomy, Stanford University.

Lecture 8

We will discuss a variety of methods for analyzing the behavior of autonomous systems.

Assignment:

• Run simulations to characterize collision avoidance performance against a variety of metrics; develop methods for visualizing the decision making behavior of your system.

Measuring System Effectiveness

It is the designer's responsibility to go back to the field and assess the impact that the autonomous system is having. This measurement process must be both qualitative and quantitative.

Qualitative: Deals with the quality of a result. Does the policy followed by the agent look good? Is it behaving reasonably?

Quantitative: Objective values that can be quantified. For example, with ACAS X, one should look at operational data on airborne collisions, near-misses, and separation after ACAS X has been put into place.

Reward

Autonomous agents are often trained to maximize their reward. Does your agent receive high reward? That's all you care about, right?

Wrong.

We care about the performance of the system in the real world, and the real world is never perfectly modeled.

The Pareto Frontier

When optimizing a real-world system one often must balance a large number of trade-offs.

Which of the following is better?

• an airborne collision avoidance system that has $1$ collision and $1000$ alerts per million flight hours

• an airborne collision avoidance system that has $2$ collisions and $10$ alerts per million flight hours

Fewer collisions are good, and fewer alerts are good, but we cannot say which collision system is better without making a judgement on their relative value.

We know, therefore, that if we have a set of policies:

The policies that are potentially the best are those which cannot be shifted to be made better in both respects:

The Pareto Frontier is obtained by adjusting the tradeoff between your multiple objectives and optimizing models to trace out the curve.

The region closer to the origin than the Pareto Frontier is infeasible, whereas the region farther from the origin than the Pareto Frontier is suboptimal.

Given a Pareto Frontier, how do we choose the best policy?

This is often a subjective question, and often requires the careful consideration of factors that are not in your optimization objective. Domain experts are often consulted.

Inspect the Decision Making Behavior

Has your agent really learned to do what it was designed to do?

If you have trained a neural network to recognize cats, how do you know whether the neural network has really learned what a cat is?

Below we see the result of optimizing a neural network trained to recognize dumbbells. It turns out that the net sees dumbbells as dumbbells with forearms.

The Black Swan Problem

This problem is known as the Black Swan Problem. The problem gets its name from the black swans of Australia and New Zealand, and the incorrect induction followed by a European:

All swans I have seen are white, therefore all swans are white

Of course, once said European goes to southern Australia and sees a black swan they can either change their belief or forever categorize the black swan as an entirely different species.

With autonomous agents we want to make sure that they identify the correct categories. It is often a non-trivial problem.

For an Autonomous Car, are these Pedestrians?

Sure looks like a pedestrian.

Also a pedestrian–-but this one also has a bike. Maybe our definition should be "A person walking across the street".

Whoops! That didn't work. Hmm. Harder than we thought!

How to Get Past the Black Swan Problem

The Black Swan problem is a fundamental problem in artificial intelligence and machine learning. The best way around it is to have as large and comprehensive dataset as possible and to test on as many corner cases as possible. Visualize your agent's decision making process!

Cross Validation

In this class you are trying to optimize an airborne collision avoidance system. You have been given a dataset of encounters. How do you go about tuning your model parameters for maximum performance?

• Maximize Performance on the Given Dataset

This option is very tempting. You simply optimize the system to maximize the reward when run in simulation on the training set. What could go wrong?

Let us provide an illustrative example: adjusting the number of histogram bins to get the best fit for a distribution.

Consider the following true distribution:

You want to get the best model for this distribution. The problem is, all you have to train on is a sample dataset:

Suppose we want to use a piecewise uniform distribution with even bin widths. Above I used 20 bins to create one. How do we select the best number of bins?

Clearly the correct number is somewhere between 5 and 100, but what should we use? Remember, we don't have access to the true distribution.

One approach to use is to do a train-test split.

This involves taking the available data and using some to fit the distribution and the rest to check the fitness:

We can then use some metric, perhaps the likelihood of the test data under the learned model, to select the preferred nbins.

This approach tests the ability of your model to generalize to unseen data.

Two things:

1. Notice how small the likelihoods are? Maximizing the log-likelihood gives the same result but with nicer numbers

2. Notice those zeros? Those occur whenever we have a training sample with zero likelihood. We can add a prior of one count to each bin to ensure that we get some support. This is also called Laplace smoothing.

Train-test splitting is pretty good, but we can do even better if we do this over multiple train-test splits. Cross validation is one common way of doing this.

In $k$-fold cross validation, you take your training data and divide it into $k$ even chunks. For each chunk, you

• train on all of the $k-1$ other chunks

• test on the chunk

And then take the average over all $k$ validation scores to get your cross-validated score.

Measuring the 'Closeness' of Distributions

One often needs to measure the closeness of two distributions, such as when comparing distributions over emergent metrics to their real-world counterparts.

For example, if you create a car that is supposed to drive like a human, does it tend to drive with the same following distance as a real car does?

We can all agree that the following two distributions are close.

We can all agree that the following two distributions are less close.

How close are these distributions?

The Kullbeck–Leibler divergence is one way to measure closeness. It actually measures divergence, the opposite of closeness.

$$D_{KL}(p\mid \mid q)={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}p(x)\log \frac{p(x)}{q(x)}dx$$

It is $0$ if the two distributions are the same and increases if they are different.

Note that it is non-symmetric, so $D_{KL}(p\mid \mid q)\ne D_{KL}(q\mid \mid p)$. Here, $p$ is the true distribution and $q$ is what is being used to approximate $p$.

The KL divergence for two Gaussian distributions $p=\mathcal{N}({\mu }_1,{\sigma }_1)$ and $q=\mathcal{N}({\mu }_2,{\sigma }_2)$ is:

$$D_{KL}(p\mid \mid q)=\log \left(\frac{{\sigma }_2}{{\sigma }_1}\right)+\frac{{\sigma }_1^2+({\mu }_1-{\mu }_2{)}^2}{2{\sigma }_2^2}-\frac{1}{2}$$

Assignment

Your homework is to:

• Run your collision avoidance system on the training set and pick three encounters where the system fails. Why does it fail? Is this a problem with your design? How might it be fixed?

• Run your collision avoidance system on the training set and compute:

  • the number of NMACs

  • the number of NMACs in which no advisory was issued

  • a histogram over the aircraft separation distance when advisories were issued

  • a scatter plot of relative horizontal separation vs. relative vertical separation when advisories were issued

  • a scatter plot of vehicle bearing the clockwise bearing from your craft to the intruder at the encounter start vs. the clockwise heading of the intruder relative to the positive north axis (See Lecture 4) for when advisories were issued

• Choose a meaninful tuneable parameter in your collision avoidance system, or change your system to include a meaningful tuneable parameter. (For example, a parameter in the Alpha-Beta filter). Use $5$-fold cross validation over the training dataset and plot the cross-validated-normalized-penalty with respect to the tuneable parameter.

Turn in your code and writeup (preferably a single Julia Notebook) to Canvas.